package leetcode.editor.cn;
 
/**
 * 目标和
 * @author qulq
 * @date 2024-07-23 21:15:23
 */
public class T494_TargetSum{
	 public static void main(String[] args) {
	 	 // 测试代码
	 	 Solution solution = new T494_TargetSum().new Solution();
	 }

	/**
	 * left：下标为 "+" 的元素的和
	 * right：下标为 “-” 的元素的和
	 * 因为 left + right = sum
	 * left - right = target
	 * 所以得到：left = (sum + target) / 2
	 * 问题转化为：在集合nums中找出和为left的组合
	 */
// 力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
		int sum = 0;
		for (int num : nums) {
			sum += num;
		}
		// 如果target的绝对值大于sum，那么是没有方案的
		if (Math.abs(target) > sum) {
			return 0;
		}
		// 如果(target+sum)除以2的余数不为0，也是没有方案的
		if ((target + sum) % 2 == 1) {
			return 0;
		}
		int bagSize = (target + sum) / 2;
		int[] dp = new int[bagSize + 1];
		// 当i = 0时，因为 f[1] = f[1] + f[1-1] 明显需要等于1，所以f[0] 初始化为 0
		dp[0] = 1;
		for (int i = 0; i < nums.length; i++) {
			for (int j = bagSize; j >= nums[i]; j--) {
				dp[j] = dp[j] + dp[j - nums[i]];
			}
		}
		return dp[bagSize];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}